// https://leetcode.cn/problems/longest-common-prefix/description/

// 算法思路总结：
// 1. 纵向扫描所有字符串的同一列字符
// 2. 比较每个字符串当前位置的字符是否相同
// 3. 遇到不同字符或字符串结束立即返回
// 4. 时间复杂度：O(n*m)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        int n = strs.size();
        if (n == 1) return strs[0];

        string res;
        for (int i = 0 ; i < strs[0].size() ; i++)
        {
            char ch = strs[0][i];
            for (int j = 1 ; j < strs.size() ; j++)
            {
                if (i >= strs[j].size() || strs[0][i] != strs[j][i])
                    return res;
            }
            res += ch;
        }

        return res;
    }
};

int main()
{
    vector<string> strs1 = {"flower","flow","flight"};
    vector<string> strs2 = {"dog","racecar","car"};

    Solution sol;
    cout << sol.longestCommonPrefix(strs1) << endl;
    cout << sol.longestCommonPrefix(strs2) << endl;

    return 0;
}